package com.study.leetcode;

public class _64 {
    public int minPathSum(int[][] grid) {
        int[][] cache = new int[grid.length][grid[0].length];
        int val = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                val = grid[i][j];
                if (i == 0 && j == 0) {
                    cache[i][j] = val;
                } else if (i == 0) {
                    cache[i][j] = cache[i][j - 1] + val;
                } else if (j == 0) {
                    cache[i][j] = cache[i - 1][j] + val;
                } else {
                    cache[i][j] = Math.min(cache[i - 1][j], cache[i][j - 1]) + val;
                }
            }
        }
        return cache[cache.length - 1][cache[0].length - 1];
    }

    public static void main(String[] args) {
        _64 v = new _64();
        System.out.println(v.minPathSum(new int[][]{{1,3,1},{1,5,1},{4,2,1}}));
    }
}
